package threshold;

import com.njupt.Tree.TreeNode;

/**
 * @Author wujiaming
 * @Description TODO
 * @Date 2023-03-07 17:06
 * @Version 1.0
 */
public class IsBalanced {

    /**
     * 判断是否为平衡二叉树，先序遍历二叉树，遍历的同时分别计算左右子树的高度，若左右字数差为y一则是平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null){return true;}
        int lDepth = depth(root.left);
        int rDepth = depth(root.right);
        return (Math.abs(lDepth-rDepth)<=1) && isBalanced(root.left) && isBalanced(root.right);
    }

    /**
     * 计算二叉树的高度
     * @param root
     * @return
     */
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        int lDepth = depth(root.left);
        int rDepth = depth(root.right);
        return lDepth<rDepth?rDepth+1:lDepth+1;
    }


    public static void main(String[] args) {

    }
}
